The Twofish Encryption Algorithm: A 128-Bit Block Cipher by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817   Pub Date: 03/01/99

Preface

AES

NIST, the National Institute of Standards and Technology, is replacing the DES encryption algorithm. The new algorithm will be called AES (Advanced Encryption Standard), will have a longer key length (128-, 192-, and 256-bit) and a larger block size (128-bit), be faster than triple DES (and probably DES), and hopefully will remain strong for a long, long time.

The process is an interesting one. In 1997, NIST sent out a request for candidate algorithms. They received fifteen submissions by the June 1998 deadline, five from the U.S. and ten from other countries. In the weeks that followed, most of the submitters posted their algorithms on the World Wide Web. In August 1998, all the submitters presented their algorithms to the world at the First AES Candidate Conference.

There will be a Second AES Candidate Conference in Rome in March 1999, where people will present papers analyzing the algorithms. Through June 1999, NIST is soliciting public comment. Then NIST will choose about five algorithms to go into the second round and, after another comment period and a third conference (sometime in mid-2000), they will choose one to turn into the standard. Then, NIST will write a FIPS, a Federal Information Processing Standard for the new algorithm, and hopefully the AES will be adopted by other standards bodies throughout the world.

All fifteen algorithms are new. Existing ones, like triple-DES, IDEA, RC5, and Blowfish, were not eligible because their block sizes were too small was not eligible because its block and key size were both too small.

The NSA did not submit any algorithm. They had one ready, but NIST preferred to use them as an independent evaluator. Of course, their classified analysis will not be made public, but NIST hopes that the public comments will recommend the same algorithms that the NSA’s analysis does.

NIST required that all submitters state that if their algorithm was chosen as AES, they would give up all patent rights. Some submitters have given up patent rights regardless, others are holding on to their patent rights until they are chosen (and will keep them if they axe not chosen). Some people chose not to submit their algorithms under these circumstances, stating that they do not want to give up the ability to charge for their algorithms. But since NIST received some very high-quality designs from groups that were willing to give them away for free, it seems NIST was correct in demanding patent-free submissions.

Cryptographers are busily analyzing the submissions for security. It’s tempting to think of the process as a big demolition derby: everyone submits their algorithms and then attacks all the others . . . the last one standing wins. Really, it won’t be like that.

At the time of writing (November 1998), there has been some pretty devastating cryptanalysis against three of the weaker candidates. (One was broken minutes after it was presented.) By the end of the first comment period, we expect there to be weaknesses found in only a few others. We strongly believe that at the end of the process most of the candidates will be unbroken. The winner will be chosen based on other factors: performance, flexibility, suitability.

AES will have to work in a variety of current and future applications, doing all sorts of different encryption tasks. Specifically:

•  AES will have to be able to encrypt bulk data quickly on top-end 32-bit CPUs and 64-bit CPUs. The algorithm will be used to encrypt streaming video and audio to the desktop in real time.

•  AES will have to be able to fit on small 8-bit CPUs in smart cards. To a first approximation, all DES implementations in the world are on small CPUs with very little RAM. It’s in burglar alarms, electricity meters, pay-TV devices, and smart cards. Sure, some of these applications will get 32-bit CPUs as those get cheaper, but that just means that there will be another set of even smaller 8-bit applications.

•  AES will have to be efficient on the smaller, weaker, 32-bit CPUs. Smart cards won’t be getting Pentium-class CPUs for a long time. The first 32-bit smart cards will have simple CPUs with a simple instruction set. 16-bit CPUs will be used in embedded systems that need more power than an 8-bit CPU, but can’t afford a 32-bit CPU.

•  AES will have to be efficient in hardware, in not very many gates. There axe lots of encryption applications in dedicated hardware: contactless cards for fare payment, for example.

•  AES will have to be key agile. There are many applications where small amounts of text are encrypted with each key, and the key changes frequently. This is a very different optimization problem than encrypting a lot of data with a single key.

•  AES will have to be able to be parallelized. Sometimes you have a lot of gates in hardware, and raw speed is all you care about.

•  AES will have to work on DSPs. Sooner or later, your cell phone will have proper encryption built in. So will your digital camera and your digital video recorder.

•  AES will need to be secure as a hash function. There are many applications where DES is used both for encryption and authentication; there just isn’t enough room for a second cryptographic primitive. AES will have to serve these same two roles.

•  AES needs to be secure for a long time. Infrastructure is hard to update. Like DES, AES hardware is likely to be installed and used for decades. A radical new algorithm, with interesting and exciting ideas, just doesn’t make sense. A conservative algorithm is what is needed.

Choosing a single algorithm for all these applications is not easy, but that’s what we have to do. It might make more sense to have a family of algorithms, each tuned to a particular application, but there will be only one AES. And when AES becomes a standard, customers will want their encryption products to be “buzzword compliant.” They’ll demand it in hardware, in desktop computer software, on smart cards, in electronic-commerce terminals, and in other places we never thought it would be used. Anything we pick for AES has to work in all those applications.

We designed Twofish with this in mind. It’s the fastest submission on the Pentium, second fastest on the Pentium Pro/Pentium 11, efficient on RAM-poor smart cards (some other algorithms can’t even fit on some smart cards), implementable in hardware at either high speeds or low gate count, and suitable to be used in a hash function. It’s flexible enough for implementations where one key encrypts megabytes, and for implementations where the key changes with each block.

For more information on the AES process, visit the NIST AES home page at http://www.nist.gov/slash aes. A general performance comparison of all the AES candidates can be found at http: //www.counterpane.com/aes-performance.html [SKW+99a]; see also Brian Gladman’s work at http://www. seven77.demon.co.uk/aes.htm. For a summary of the most recent attacks against the different candidates, see Lars Knudsen’s summary at http://www.ii.uib.no/~larsr/aes.html.

This Book

This book contains all the details about Twofish, from the design criteria to the best cryptanalysis at the time of writing (November 1998). It is based on the original Twofish AES submission [SKW+98a], but also includes the first three Twofish Technical Reports [Fer98b, WW98, WS98] and the various Twofish articles and papers [SKW+98b, Sch98, SKW+99b].

This book does not contain information about the other fourteen AES submissions, or any comparisons of Twofish with them. Since this book is about the design of Twofish, which was completed without seeing the other AES submissions (except for LOKI97 and a preliminary version of Serpent, which were published early), we felt that it would be inappropriate to discuss the other submissions in this book.

As analysis progresses, more will become known about Twofish. The latest information can always be found on the Twofish web site:

http://www.counterpane.com/twofish.html

The web site also contains downloadable Twofish source code:

•  Reference C implementation.

•  Optimized C for the Intel Pentium, Pentium Pro, and Pentium II.

•  Assembly code for the Intel Pentium, Pentium Pro, and Pentium II.

•  6805 assembly code.

Additional implementations will be added when they become available.

The authors would like to thank Carl Ellison, Nina Fefferman, Paul and Randy Milbert, who read and commented on drafts of the original AES submission, and Beth Riedman, who copyedited the manuscript twice (both the original AES submission and this book). Additionally, the authors would like to thank NIST for initiating the AES process, Miles Smid, Jim Foti, and Ed Roback for putting up with a never-ending stream of questions and complaints about its details, and all the other AES candidates for submitting their algorithms, and making the AES selection process so interesting. We know how much effort they all went through.

This work has been funded by Counterpane Systems and Hi/fn Inc.